iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 8
1

佇列其資料結構用圖片來說明大概如下:

資料以一列的方式儲存每個資料,而且刪除節點時會從最前面也是最早加入佇列的資料開始刪除,新增節點從佇列尾巴開始刪除。此為佇列 先進先出(FIFO, First-In-First-Out) 的特性。

佇列只允許在後端(稱為Rear)進行插入操作,在前端(稱為Front)進行刪除操作

佇列的兩種操作函式:

  • enqueue(adding, offering):將資料放入佇列尾端
  • dequeue(polling):取出佇列前端之資料

常見範例:

  • 人們排隊
  • 寫入磁碟的資料先儲存在電腦的記憶體緩衝區中
  • Breadth-First Search(BFS,廣度優先搜尋)

對於佇列有初步了解後,我們來實作吧!這裡使用 Linked List 當作基礎的資料結構去做實作。

先定義出Queue類別及它的節點

class QueueNode {
  constructor(data, next) {
    this.data = data
    this.next = next
  }
}

class Queue {
  constructor() {
    this.front = null
    this.tail = null
  }

  // 判斷佇列是否為空,直接判斷最前面節點是否為空即可
  isEmpty() {
    return this.front === null
  }

  // 新增節點
  enqueue(value) {

  }

  // 移除節點
  dequeue() {

  }
}

完成 enqueue() 函式:

邏輯相當的簡單,記得是從尾巴新增節點喔~

enqueue(value) {
  let node = new QueueNode(value)
  if (this.isEmpty()) {
    this.front = node
    this.tail = node
  } else {
    // 讓尾巴節點先指向node新節點
    this.tail.next = node
    // 讓新節點變成新的尾巴節點
    this.tail = node
  }
}

完成 dequeue() 函式:

將原本前面第二個節點變成第一個節點即可

dequeue() {
  let result = this.front.data
  // 空佇列的狀況
  if (this.isEmpty()) {
    return null
  }

  if (this.front === this.tail) { // 變成空佇列
    this.front = null
    this.tail = null
  } else {
    // 使原本前面第二個節點變成第一個節點
    this.front = this.front.next
  }

  return result
}

最後建立 qq 物件,並使用enqueue()和dequeue()進行操作

let qq = new Queue()
qq.enqueue("A")
qq.enqueue("B")
qq.enqueue("C")
qq.enqueue("D")
qq.enqueue("E")

while (!qq.isEmpty()) {
    console.log(qq.dequeue()) // A B C D E
}

佇列的時間複雜度

可參考 Time and Space Complexity of Queue

https://ithelp.ithome.com.tw/upload/images/20230419/20116883U0aAboazuv.png

這次文章的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day8-queue.js

以上就是這次關於佇列的介紹,明天我們將用佇列解決一個找質數問題!


上一篇
Day7-利用堆疊解決"平衡括號"問題
下一篇
Day9-使用佇列實作質數篩選
系列文
使用JavaScript學習資料結構與演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言